package cn.itcast.zt.leetcode.tree;

import cn.itcast.zt.leetcode.element.TreeNode;

import java.util.*;

/**
 * 树相关的算法合集
 */
public class Tree_Algorithm {
    /**
     * 二叉树的层次遍历 102
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>() ;

        if (root == null) {
            return ret ;
        }

        Queue<TreeNode> queue = new LinkedList<>() ;
        queue.offer(root) ;

        while(!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>() ;
            int curentLevelSize = queue.size();
            for(int i = 1; i <= curentLevelSize; i++) {
                TreeNode node = queue.poll() ;
                level.add(node.val) ;

                if (node.left != null) {
                    queue.offer(node.left) ;
                }

                if (node.right != null) {
                    queue.offer(node.right) ;
                }
            }

            ret.add(level) ;
        }

        return ret ;
    }

    /**
     * 二分查找  704
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1 ;
        }

        int numsLength = nums.length ;
        int start = 0 ;
        int end = numsLength - 1 ;

        while(start <= end) {
            int mid = start + (end - start) / 2 ;
            if (target > nums[mid]) {
                start = mid + 1 ;
            }else if(target < nums[mid]) {
                end = mid - 1 ;
            }else {
                return mid ;
            }
        }

        return -1 ;
    }

    public static void main(String[] args) {
        double sqrtV = new Tree_Algorithm().sqrt(4.0) ;
        System.out.println(sqrtV);

        int[] nums = new int[] {4,5,6,7,8,1,2,3} ;
        int target = 2 ;
        System.out.println(searchTargetIndex(nums, target)) ;
    }

    /**
     * 给定一个旋转的有序数组，找到其中的目标元素的下标
     * 如：nums = [4,5,6,7,8,1,2,3] target = 2 返回6
     * @param nums
     * @param target
     * @return
     */
    public static int searchTargetIndex(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return -1 ; // 数组为空或为null时返回-1
        }

        int left = 0;
        int right = nums.length - 1 ;
        while(left <= right) {
            int mid = left + (right - left) / 2 ;

            // 找到目标值 返回索引
            if(target == nums[mid]) {
                return mid;
            }

            // 判断左半部分是否有序
            if (nums[left] <= nums[mid]) {
                // 目标值在有序的左半部分
                if (nums[left] <= target && nums[mid] >target) {
                    // 目标值在左半部分
                    right = mid - 1 ;
                }else {
                    // 目标值不在左半部分
                    left = mid + 1 ;
                }
            }else {// 右半部分有序
                if (nums[mid] < target && nums[right] >= target) {
                    // 目标值在右半部分
                    left = mid + 1 ;
                }else {
                    // 目标值不在右半部分
                    right = mid - 1 ;
                }
            }
        }

        return -1 ; // 未找到目标值
    }

    public double sqrt(double x) {
        if (x < 0) {
            throw new IllegalArgumentException() ;
        }

        if (x == 0 || x == 1) {
            return x ;
        }

        double left, right ;
        if(x > 1) {
            left = 1.0d ;
            right = x ;
        }else {
            left = x ;
            right = 1.0d ;
        }

        double epsilon = 1e-10 ;
        while(left <= right) {
            double mid = left + (right - left) / 2 ;
            double midSquare = mid * mid ;

            if (midSquare - x <= epsilon && midSquare - x >= epsilon * -1) {
                return mid ;
            }else if (midSquare > x){
                right = mid ;
            }else {
                left = mid ;
            }
        }

        return -1.0d;
    }

    /**
     * 二叉树的最大深度
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0 ;
        }else {
            int leftHeight = maxDepth(root.left) ;
            int rightHeight = maxDepth(root.right) ;
            return Math.max(leftHeight, rightHeight) + 1 ;
        }
    }

    /**
     * 100. 相同的树
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true ;
        }else if(p == null || q == null) {
            return false ;
        }else if (p.val != q.val) {
            return false ;
        }else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right) ;
        }
    }

    /**
     * 226. 翻转二叉树
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null ;
        }

        TreeNode left = invertTree(root.left) ;
        TreeNode right = invertTree(root.right) ;

        root.left = right ;
        root.right = left ;
        return root ;
    }

    /**
     * 230. 二叉搜索树中第K小的元素
     */
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>() ;
        while(root != null || !stack.isEmpty()) {
            while(root != null) {
                stack.push(root);
                root = root.left ;
            }

            root = stack.pop() ;
            --k ;

            if (k == 0) {
                break;
            }

            root = root.right ;
        }

        return root.val ;
    }
}
